Disclaimer

THESE MATERIALS ARE PROVIDED "AS IS" AND ALLOTROPE EXPRESSLY DISCLAIMS ALL WARRANTIES, EXPRESS, IMPLIED OR STATUTORY, INCLUDING, WITHOUT LIMITATION, THE WARRANTIES OF NON-INFRINGEMENT, TITLE, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

Document Conventions

Functional Requirements

• Storage format for RDF Statements
• Create, Read, Update and Delete (CRUD) of RDF Statements
• Query RDF Data Model

Non-Functional Requirements

• Performance: provide efficient CRUD of RDF Statements and efficient query performance
• Storage layout: provide efficient storage of resource URIs and literals
• Adaptability: to Java and .Net APIs (e.g. Apache Jena)
• Embeddability: storage format MUST be embeddable into HDF5

Dictionary

The Dictionary MUST contain the string representation of resources and literals and MUST provide efficient access to them.

Quad Table

The Quad Table represents the quads. It MUST consist of five columns - one for the graph, one for the subject, one for the predicate, one for the object of a quad and one to mark the quad as deleted. One row in the table represents one quad.

Indices

The ADF Quad Store MAY use different kinds of indices in order to improve the performance of basic operations such as inserting and querying of quads (triples into a specific graph), e.g. an GSPO index. The reference implementation uses three indices: GSPO, GPOS and GOSP. Three additional indices (SPOG, POSG and OSPG) are supported, but the current implementation would not benefit from them.

B+ Tree

In order to provide efficient dictionaries and indexing to the ADF Quad Store, ADF-QS MUST store data in a B+ Tree data structure. In the implementation, one node in the B+ Tree MUST correspond to one row in the HDF5 Dataset that is represented by the tree.

Quads

The quads MUST be stored as their node IDs in an HDF5 Dataset [[!HDF5]]. The name of the Dataset MUST be quads and it MUST be located directly in the data-description Group. This Dataset MUST have five columns - four for the node IDs and a fifth for the time of deletion of this quad. The Dataset MUST have the attributes nextID and size of type int containing the index of the next row to be used for a new quad and the current number of not-deleted entries.

A node ID is a 64 bit value with the following bit usage:

Node Strings

A quad node may consist of two strings (value and namespace, type or language). Those strings MUST be stored and accessible via a dictionary structure. The dictionary MUST consist of a part responsible for the string storage and a B+ tree for fast access. All Datasets used by the dictionary MUST be located in the Group dictionary below the Group data-description.

The B+ tree uses the string itself as the key and the technical string ID as value. On B+ tree Dataset level these are the same values since the key entry in the nodes Dataset is the ID of the key (see section B+ Tree).

The strings MUST be persisted as bytes, using UTF-8. A one dimensional HDF5 Dataset contains a continuous byte stream. A two dimensional Dataset stores position and length in the byte stream or strings up to 12 bytes length. The row ID in the second Dataset is the technical ID of the string (used as part of the quad node ID and in the dictionary B+ tree). Both Datasets MUST have an attribute nextID of type int containing the index of the next row to be used for a new entry. The following two modes of storage for those bytes MUST be supported.

B+ Tree

The HDF5 based quad store implementation MUST use B+ trees stored in HDF5 Datasets. See [[!WIKI-BP-TREE]] for terminology and functional implementation details.

The nodes of the B+ tree MUST be stored in a two dimensional Dataset with data type int. The Dataset MUST have an attribute nextID of type int containing the index of the next row to be used for a new node. The number of columns MUST be two times the tree order plus one (2 * order + 1).

Field usage:

Flags:

In contrast to the common B+ tree implementation with the HDF5 based implementation the root node MUST remain in row 0 and so MUST keep ID 0.

Index

An HDF5 based implementation SHOULD use an SPO, a POS and an OSP index as described below. It MAY use additional indexes. It MUST delete any index present that it does not update, when changing the content of the quad store. Indices MUST be based on B+ trees. The B+ tree Dataset MUST be located in a Group named index_>index name< below the data-description Group.

The default indices (GSPO, GPOS, GOSP, SPOG, POSG and OSPG) must use the quads Dataset entries as keys. These entries contain the node IDs of subject, predicate and object of the statement, and, if deleted, the deletion time, otherwise 0. The B+ tree values are the IDs of the quads Dataset entries. The name of the index defines the order for sorting those entries. The keys of an SPO index are sorted first by the subject node ID, then by the predicate node ID and last by the object node ID.

Notes on Jena Integration

To use the ADF Quad Store in Jena, the Graph and TripleStore interfaces MUST be implemented. For Graph the class GraphBase MUST be extended, which contains a lot of boilerplate code. To use the ADF based graph an instance SHOULD be passed to Jena: ModelFactory.createModelForGraph(adfGraph).